21.5 Heapsort


How can you use a Priority Queue to sort a list of items?

	for each item x
	    insert x into PQ
	while PQ not empty
	    deleteMin gives next item in sorted order


What's the running time of this algorithm?

	O(N log N)

How much space is used by this algorithm?

	N for the list
	another N for the PQ


Describe a similar algorithm that sorts in-place using only a single
array of N items.

	call buildHeap on the array of N items
	repeat N-1 times
	    swap the first item (root) with the last item
	    decrement the heap size
	    percolateDown the first item


What's the order of the items in the resulting array?

	a Min Heap gives the items in decreasing order

How can you change the algorithm to give increasing order?

	a Max Heap gives the items in increasing order


Show the result of heapsort on the array. (use a max-heap)

	8 5 2 7 3 4 6 9 2

	9 8 6 7 3 4 2 5 2| (build-heap)
	2 8 6 7 3 4 2 5| 9 (swap)
	8 7 6 5 3 4 2 2| 9 (perc)
	2 7 6 5 3 4 2| 8 9 (swap)
	7 5 6 2 3 4 2| 8 9 (perc)
	2 5 6 2 3 4| 7 8 9 (swap)
	6 5 4 2 3 2| 7 8 9 (perc)
	2 5 4 2 3| 6 7 8 9 (swap)
	5 3 4 2 2| 6 7 8 9 (perc)
	2 3 4 2| 5 6 7 8 9 (swap)
	4 3 2 2| 5 6 7 8 9 (perc)
	2 3 2| 4 5 6 7 8 9 (swap)
	3 2 2| 4 5 6 7 8 9 (perc)
	2 2| 3 4 5 6 7 8 9 (swap)
	2 2| 3 4 5 6 7 8 9 (perc)
	2| 2 3 4 5 6 7 8 9 (swap)


Classwork
You may work with a partner.
Show the result of heapsort on the array. (use a max-heap)

	7 8 8 4 5 4 3 1 2

	8 8 7 4 5 4 3 1 2| (build-heap)
	2 8 7 4 5 4 3 1| 8 (swap)
	8 5 7 4 2 4 3 1| 8 (perc)
	1 5 7 4 2 4 3| 8 8 (swap)
	7 5 4 4 2 1 3| 8 8 (perc)
	3 5 4 4 2 1| 7 8 8 (swap)
	5 4 4 3 2 1| 7 8 8 (perc)
	1 4 4 3 2| 5 7 8 8 (swap)
	4 4 1 3 2| 5 7 8 8 (perc)
	2 4 1 3| 4 5 7 8 8 (swap)
	4 3 1 2| 4 5 7 8 8 (perc)
	2 3 1| 4 4 5 7 8 8 (swap)
	3 2 1| 4 4 5 7 8 8 (perc)
	1 2| 3 4 4 5 7 8 8 (swap)
	2 1| 3 4 4 5 7 8 8 (perc)
	1| 2 3 4 4 5 7 8 8 (swap)


Explain the code for heapsort.

	void heapsort(Comparable[] array) {
	    for (int i = array.length/2; i >= 0; i--)
	        percDown(array, i, array.length);
	    for (int j = array.length-1; j > 0; j--) {
	        swap(array, 0, j);
		percDown(array, 0, j);
	    }
	}


How does a heap work with indexes starting at 0?

	the parent of the node at i is at (i-1)/2
	the left child of the node at i is at 2i+1
	the right child of the node at i is at 2i+2